1. Field of the Invention
The present invention relates to an arrangement for transforming plaintext into the corresponding ciphertext in a digital data communications system. The arrangement disclosed is also applicable to the reverse process of transforming ciphertext into the original plaintext.
2. Description of the Related Art
In a data communications system, it is a common practice to use cryptographic techniques in order to prevent an unauthorized person(s) from obtaining data. The plaintext to be transmitted is transformed into the corresponding ciphertext. The ciphertext, when received, is subject to the reverse process via which the ciphertext is transformed into the original plaintext.
A cipher is a secret method of writing whereby plaintext (or cleartext) is transformed into the corresponding ciphertext (sometimes called a cryptogram). The process is called encipherment or encryption, while the reverse process of transforming ciphertext into the corresponding plaintext is called decipherment or decryption. Both encipherment and decipherment are controlled by a cryptographic key or keys.
A known encipherment which is currently used, is to linearly transform plaintext M into the corresponding ciphertext C as shown in equation (1): EQU C=a.multidot.M+bmod N (1)
where a, b, and N each is a predetermined integer. As an example, the plaintext M is a data word having a constant bit length. As is well known in the art, "b mod N" implies a residue when "b" is divided by "N".
The ciphertext C can be transformed into the corresponding plaintext using the following equation (2). EQU M=(C-b)/a mod N (2)
Equation (2) is to determine M which satisfies EQU (C-b)-a.multidot.M mod N
For further details reference should be made to a book, entitled "Cryptograph and Data Security" by Dorothy Elizabeth Robling Denning, published by Addison-Wesley Publishing Company (reprinted with corrections, January 1983), pages 43-45.
It the following two values p and q are determined,
p=1/a mod N PA1 q=-b/a mod N PA1 C=b mod N (M=0) PA1 C=a+b mod N(M-1) PA1 a.multidot.M(j)+b-C(j) (j=1, . . ., L) is calculated. In more specific terms, the difference between C and "a.multidot.M+b" is a multiple of N, and as such, if the greatest common measure regarding arbitrary plaintext-ciphertext pairs are determined, then the greatest common measure is equal to "N". For details reference should be made to the above-mentioned book, pages 66-67.
then the above-mentioned encipherment can be implemented by the linear transformation shown in equation (3). EQU M=p.multidot.C+q mod N (3)
In the conventional linear transformation, either of a and b (or both) is used as a cryptographic key, while N is a given constant value selected from values which may appear in the plaintext. The linear transformation can easily be processed and thus has been utilized for a long time.
However, given a plurality of plaintext-ciphertext pairs (M(1), C(1)), . . . , (M(L), C(L)), then the keys a and b can be determined by solving the following linear equations (4A)-(4L). EQU C(1)=M(1).multidot.a+b mod N (4A) EQU C(L)=M(L).multidot.a+b mod N (4L)
In this case, breaking the cipher is not difficult.
Further, the cipher is particularly vulnerable if a cryptanalyst is able to input plaintext to an encipher and observe the changes in the resulting ciphertext. In this case, the residues of "a mod N" and "b mod N" can be determined without any difficulty by calculating the following equations:
Even if all the values a, b, and N in the equation C=a.multidot.M+b mod N are utilized as keys, the cipher is breakable in the case where a cryptanalyst is able to input plaintext and then observe the ciphertext thus obtained. In this case, the residues of "a mod N" and "b mod N" are first determined using the above-mentioned proccesses. Subsequently, the greatest common measure of
In order to overcome the drawbacks inherent in the encipherment using linear transformation, a Data Encryption Standard (DES) using non-linear transformation has been proposed. Although the non-linear transformation is capable of rendering cryptanalysis much more difficult, it requires a very large look-up table stored in a read-only-memory (ROM) which renders the arrangement bulky and tends to lower the transmission rate. For further details of the DEC, reference should be made to the above-mentioned book, pages 90-101.
As mentioned above, the encipher arrangement using the conventional liner transformation has encountered the drawback that the keys can easily be solved if arbitrary plaintext-ciphertext pairs be available.
Further, the DEC using non-linear transformation is able to render cryptayalysis difficult but it suffers from complicate hardware arrangement and low transmission rate.